翻訳と辞書 Words near each other ・ Erdős number ・ Erdős Prize ・ Erdős space ・ Erdősmecske ・ Erdősmárok ・ Erdős–Anning theorem ・ Erdős–Bacon number ・ Erdős–Borwein constant ・ Erdős–Burr conjecture ・ Erdős–Diophantine graph ・ Erdős–Faber–Lovász conjecture ・ Erdős–Fuchs theorem ・ Erdős–Gallai theorem ・ Erdős–Graham problem ・ Erdős–Gyárfás conjecture ・ Erdős–Hajnal conjecture ・ Erdős–Kac theorem ・ Erdős–Ko–Rado theorem ・ Erdős–Mordell inequality ・ Erdős–Nagy theorem ・ Erdős–Nicolas number ・ Erdős–Pósa theorem ・ Erdős–Rado theorem ・ Erdős–Rényi model ・ Erdős–Stone theorem ・ Erdős–Straus conjecture ・ Erdős–Szekeres theorem ・ Erdős–Szemerédi theorem ・ Erdős–Turán conjecture on additive bases ・ Erdős–Turán inequality Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Erdős–Hajnal conjecture ： ウィキペディア英語版 Erdős–Hajnal conjecture In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. More precisely, for an arbitrary undirected graph $H$, let $\backslash mathcal\_H$ be the family of graphs that do not have $H$ as an induced subgraph. Then, according to the conjecture, there exists a constant $\backslash delta\_H\; >\; 0$ such that the $n$-vertex graphs in $\backslash mathcal\_H$ have either a clique or an independent set of size $\backslash Omega(n^)$. In contrast, for random graphs in the Erdős–Rényi model with edge probability 1/2, both the maximum clique and the maximum independent set are much smaller: their size is proportional to the logarithm of $n$, rather than growing polynomially. Ramsey's theorem proves that no graph has both its maximum clique size and maximum independent set size smaller than logarithmic. This conjecture is due to Paul Erdős and András Hajnal, who proved it to be true when $H$ is a cograph. They also showed, for arbitrary ''H'', that the size of the largest clique or independent set grows superlogarithmically. As of 2014, however, the full conjecture has not been proven, and remains an open problem. == References == *. *. *. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Erdős–Hajnal conjecture」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.